A digital signature is an encrypted message which can be used to prove that person A sent a message M (e.g., a contract) to person B. The digital signature is used both to prove that A sent the message, and also to prove that message M is in fact the message that A sent with the digital signature.
Digital signatures were invented to solve a major difficulty which has limited the application of conventional cryptography, i.e., its inability to deal with the problem of dispute. Conventional authentication systems can prevent third party forgeries, but cannot settle disputes between the sender and receiver as to what message, if any, was sent.
In current commercial practice, the validity of contracts and agreements is guaranteed by handwritten signatures. A signed contract serves as proof of an agreement which the holder can present in court if necessary, but the use of signatures requires the transmission and storage of written documents. This presents a major barrier to more widespread use of electronic communications in business.
The essence of a signature is that although only one person can produce it, anybody can recognize it. If there is to be a purely digital replacement for this paper instrument, each user must be able to produce messages whose authenticity can be checked by anyone, but which could not have been produced by anyone else, especially the intended recipient. In a conventional system the receiver authenticates any message he receives from the sender by deciphering it in a key which the two hold in common. Because this key is held in common, however, the receiver has the ability to produce any cryptogram that could have been produced by the sender and so cannot prove that the sender actually sent a disputed message.
Public key cryptosystems can provide a direct solution to the signature problem. However it is possible to generate digital signatures without using public key cryptosystems, and the present invention is such a system.
It should be noted that one of the primary purposes of public key systems is to securely convey secret information, whereas the purpose of digital signature systems is only to authenticate messages (which may or may not be secret).
In general, a person A who digitally signs a message has secret information that only he knows which allows him to do this. Thus, A knows a secret signing key herein called SIGN.sub.A. This secret signing key is not known to anyone else, nor would it ever be revealed -- even to a judge in the event of a dispute.
If person B receives a digitally signed message from A that has been signed with SIGN.sub.A, and yet B does not know what SIGN.sub.A is, then B must have some other information that allows verification of the signature. This information we call a verifying key VERIFY.sub.A. VERIFY.sub.A must be known to B and in general we assume that VERIFY.sub.A is public knowledge.
Using the present invention, A can easily generate a unique digital signature for any message M, but no one else can generate this digital signature. An important aspect of the present invention, and any useful digital signature system, is that anyone who knows VERIFY.sub.A can verify that a digitally signed message M was signed by A, and has not been altered.
In a system in which many users wish to sign and verify messages, it is necessary to generate many pairs of keys. That is, if users A, B, C, D and E all wish to sign and verify messages then the key pairs
______________________________________ SIGN.sub.A VERIFY.sub.A SIGN.sub.B VERIFY.sub.B SIGN.sub.C VERIFY.sub.C SIGN.sub.D VERIFY.sub.D SIGN.sub.E VERIFY.sub.E ______________________________________
must exist.
Each user must know his own signing key, and must not know any other user's signing key. All users must know all the verification keys.
While other digital signature systems have been proposed that rely only on conventional encryption functions, or on one way functions, none has quite succeeded in providing the convenience of systems based on more complex mathematical problem. such as factoring. Note that the RSA public key cryptosystem is based on factoring.
U.S. Pat. No. 4,309,569 describes a digital signature for authenticating messages. This digital signature utilizes an authentication tree function of a one way function. Furthermore, it is pre-certified to the extent that the underlying encryption function has been certified. The method described in U.S. Pat. No. 4,309,569 is an improvement over the prior methods in that it eliminates the large storage requirement of the prior methods. This method was therein coined "tree authentication" because it uses a binary (or K-ary) tree of recursive calls to a one way function to authenticate a digital signature.
A full explanation of the digital signature method disclosed in U.S. Pat. No. 4,309,569, can be found in chapter 5 of Secrecy, Authentication and Public Key Systems, by Dr. Ralph Merkle, UMI Research Press (1982).
A significant limitation of the digital signature method disclosed in U.S. Pat. No. 4,309,569 is that each tree function is useful for signing only a limited, preselected number of messages. In particular, when a tree is defined it has a fixed number of leaf nodes, and each leaf node can only be used once. When all the leaf nodes of the tree have been used, a new tree must be set up. Another problem, is that a large precomputation is required to set up a new tree. This makes it inconvenient to set up large trees which will be useable for signing thousands or millions of messages.
The present invention provides an infinite tree of one time signatures. As will be explained below, the present invention provides a relatively convenient method of generating digital signatures for an infinite (i.e., indefinite or unlimited) number of messages. It also avoids the need for an expensive precomputation. It should also be noted that even though the present invention uses a "tree", both the method of the present invention, and the "tree" used by this method are quite different than the "tree" used in U.S. Pat. No. 4,309,569. In fact, a wide variety of tree data structures are used in computer science for a very wide variety of functions, and, as will be evident to those who consider the matter, the tree used in the present invention has a different data structure and is used in a different manner than the tree in U.S. Pat. No. 4,309,569.
As will described in more detail below, advantages and features of the present invention include the infinitely expandability of the signature tree, dependable verification of messages based on the use of secure one time signatures (e.g., which may be based one way functions), the small amount of computation required to set up a signature tree, the small amount of storage required to maintain a tree, and the ability to implement the invention using high speed conventional encryption equipment and methods.